package 基于LRU算法的缓存;

import java.util.HashMap;
import java.util.LinkedList;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 25228
 * Date: 2024-11-25
 * Time: 14:51
 */
public class Main {
    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(3);
        cache.put(1, "one");
        cache.put(2, "two");
        cache.put(3, "three");
        System.out.println(cache.get(1)); // Returns "one"
        cache.put(4, "four");            // Evicts key 2
        System.out.println(cache.get(2)); // Returns null
        System.out.println(cache.get(3)); // Returns "three"
        System.out.println(cache.get(4)); // Returns "four"
    }
}

class Node<K,V>{
    K key;
    V value;
    Node<K, V> prev;
    Node<K, V> next;

    Node(K key, V value) {
        this.key = key;
        this.value = value;
    }
}

class LinkList<K,V>{
    Node<K, V> head;
    Node<K, V> tail;

    LinkList() {
        head = new Node<>(null, null); //哑节点
        tail = new Node<>(null, null); //哑节点
        head.next = tail;
        tail.prev = head;
    }

    //添加
    void add(Node<K,V> node){
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    //删除
    void remove(Node<K,V> node){
        node.prev.next=node.next;
        node.next.prev = node.prev;
    }

    //移动至头
    void moveToHead(Node<K,V> node){
        remove(node);
        add(node);
    }

    //得到尾节点
    Node<K,V> getTail(){
        return tail.prev;
    }

    //删除尾节点
    void removeTail(){
        Node<K,V> node=tail.prev;
        remove(node);
    }
}

class LRUCache<K, V>{
    HashMap<K,Node<K,V>> map;
    LinkList<K,V> list;
    int size;
    //接受缓存的最大容量和一个可选的回调函数作为参数，初始化缓存。
    public LRUCache(int size){
        this.size=size;
        map=new HashMap<>(size);
        list=new LinkList<>();
    }
    //方法用于向缓存中添加或更新数据项。
    public void put(K key, V value) {
        Node<K, V> node = map.get(key);
        if (node == null) {
            if (map.size() >= size) {//为空且无缓存空间
                Node<K, V> tail = list.getTail(); // 获取尾节点（不是哑节点）
                map.remove(tail.key); // 从哈希表中移除尾节点
                list.removeTail(); // 从链表中移除尾节点
            }
            Node<K, V> newNode = new Node<>(key, value);
            list.add(newNode);
            map.put(key, newNode);
        } else {//不为空更新数据
            node.value = value;
            list.moveToHead(node);
        }
    }
    //方法用于从缓存中获取指定键的数据项。
    public V get(K key) {
        Node<K, V> node = map.get(key);
        if (node == null) {
            return null;
        }
        list.moveToHead(node);
        return node.value;
    }
}